package 图.岛屿问题;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/8 21:43
 */
public class lc827最大人工岛 {
    /*
        DFS + 沉岛 + Map


        一些细节点:
        ① 如果整个 网格 是一个完整的岛屿, 这种情况需要特判

        ② 存在 一个 点的 上下左右方向 的相邻岛屿 是 同一个 岛, 所以要用set 来去重一下!


     */

    int dir[][] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    int no = 2, ans = 0;
    Map<Integer,Integer> map = new HashMap<>();
    public int largestIsland(int[][] grid) {
        // 把岛屿 进行编号
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] == 1){
                    int dfs = dfs(i, j, no, grid);
                    map.put(no ++,dfs);
                }
            }
        }

        // 开始尝试 连通 0 ---> 1
        boolean flag = true; // 如果 到 遍历完整个 网格 最后 flag 任然是 true 说明整个网格就是一个岛
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int temp = 0;
                Set<Integer> set = new HashSet<>(4); //  存在四个方向重复添加的问题, 存在两个以上方向相邻岛屿 是 同一个 no 编号的岛屿
                if(grid[i][j] == 0){
                    flag = false;
                    for(int []d : dir){
                        int x = d[0] + i;
                        int y = d[1] + j;
                       if(x < 0 || x == grid.length || y < 0 || y == grid[0].length || grid[x][y] == 0){
                           continue;
                       }
//                       temp += map.get(grid[x][y]); 存在重复 累加
                        set.add(grid[x][y]);
                    }
                }
                for (int num : set){
                    temp += map.get(num);
                }
                ans = Math.max(ans,temp);
            }
        }
        return flag ?  map.get(2) :ans + 1;
    }

    public int dfs(int i, int j, int no, int martix[][]) {
        if (i < 0 || j < 0 || i == martix.length || j == martix[0].length || martix[i][j] != 1) {
            return 0;
        }
        int ans = 1;
        martix[i][j] = no; // 标记一下, 这片岛的编号 number
        for (int[] d : dir) {
            int x = d[0] + i;
            int y = d[1] + j;
            ans += dfs(x,y,no,martix);
        }
        return ans;
    }


}
/*
 三叶姐的题解: 差不多也是你认为的那个对应关系
 而且 她这个并查集的我板子, 也是跟  你的这套差不多!
 */
class Solution {
    static int N = 510;
    static int[] p = new int[N * N], sz = new int[N * N];
    int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return ;
        if (sz[ra] > sz[rb]) {
            union(b, a);
        } else {
            sz[rb] += sz[ra]; p[ra] = p[rb];
        }
    }
    public int largestIsland(int[][] g) {
        int n = g.length;
        for (int i = 1; i <= n * n; i++) {
            p[i] = i; sz[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 0) continue;
                for (int[] di : dirs) {
                    int x = i + di[0], y = j + di[1];
                    if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
                    union(i * n + j + 1, x * n + y + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) {
                    ans = Math.max(ans, sz[find(i * n + j + 1)]);
                } else {
                    int tot = 1;
                    Set<Integer> set = new HashSet<>();
                    for (int[] di : dirs) {
                        int x = i + di[0],y = j + di[1];
                        if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == 0) continue;
                        int root = find(x * n + y + 1);
                        if (set.contains(root)) continue;
                        tot += sz[root];
                        set.add(root);
                    }
                    ans = Math.max(ans, tot);
                }
            }
        }
        return ans;
    }
}